package com.zj.leetcode.medium.greed;

import java.util.Arrays;

/**
 * @program: algorithm
 * @description:
 * 最短无序连续子数组
 * 581 shortest-unsorted-continuous-subarray
 * @author: Zhang Bo
 * @create: 2022-04-08 10:43:08
 **/
public class ShortestUnsortedContinuousSubarray{
    public static void main(String[] args) {
        int[] nums = {2,6,4,8,10,9,15};
        Solution solution = new ShortestUnsortedContinuousSubarray().new Solution();
        System.out.println(solution.findUnsortedSubarray(nums));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        /**
         * 排序+遍历
         * @param nums
         * @return
         */
        public int findUnsortedSubarray(int[] nums) {
            int[] sorts =
                    Arrays.stream(nums)
                            .sorted()
                            .toArray();

            int l = -1;
            int r = -1;
            for (int i = 0; i < nums.length; i++) {
                if(sorts[i] != nums[i] && l == -1){
                    l = i;
                }
                if(sorts[i] != nums[i]){
                    r = i;
                }
            }
            return r - l == 0 ? 0 : r - l +1;

        }

        /**
         * 逆向思维
         * 如果有序最小的一定在最左边，最大的一定在最右边，然后去解这道题。
         * @param nums
         * @return
         */
        public int findUnsortedSubarray01(int[] nums) {
            if(nums == null || nums.length <= 1 ){
                return 0;
            }
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;

            int l = 0;
            int r = 0;
            for (int i = 0; i < nums.length; i++) {
                if(max > nums[i]){
                    r = i;
                }
                max = Math.max(max, nums[i]);
            }

            for (int i = nums.length - 1; i >= 0; i--) {
                if(min < nums[i]){
                    l = i;
                }
                min = Math.min(min, nums[i]);
            }

            return r - l == 0 ? 0 : r - l +1;
        }



    }
//leetcode submit region end(Prohibit modification and deletion)

}
